<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 分隔数组以得到最大和 -->
    <script>
      var maxSumAfterPartitioning = function (arr, k) {
        let len = arr.length
        let dp = new Array(len + 1).fill(0)
        //外层循环一遍
        //动态规划方程为 dp[i] = Math.max(dp[i],dp[j]+(i-j)*max)
        //第i个 为 第j个 加上i到j之间最大的值✖️数量 j倒数从i往前推k位
        for (let i = 1; i <= len; i++) {
          let max = 0
          for (let j = i - 1; i - j <= k && j >= 0; j--) {
            max = Math.max(max, arr[j])
            dp[i] = Math.max(dp[i], dp[j] + (i - j) * max)
          }
        }
        return dp[len]
      }
      console.log(maxSumAfterPartitioning([1, 15, 7, 9, 2, 5, 10], 3))
    </script>
  </body>
</html>
